<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">PEGASOS SVM solver </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p><a class="el" href="pegasos_8h.html">pegasos.h</a> provides a basic implementation of the PEGASOS <a class="el" href="citelist.html#CITEREF_shalev-shwartz07pegasos">[9]</a> linear SVM solver.</p>
<ul>
<li><a class="el" href="pegasos.html#pegasos-overview">Overview</a><ul>
<li><a class="el" href="pegasos.html#pegasos-algorithm">Algorithm</a></li>
<li><a class="el" href="pegasos.html#pegasos-bias">Bias</a></li>
<li><a class="el" href="pegasos.html#pegasos-restarting">Restarting</a></li>
<li><a class="el" href="pegasos.html#pegasos-kernels">Non-linear kernels</a></li>
</ul>
</li>
</ul>
<h2><a class="anchor" id="pegasos-overview"></a>
Overview</h2>
<p>PEGASOS solves the <em>linear</em> SxVM learning problem</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \min_{w} \frac{\lambda}{2} \|w\|^2 + \frac{1}{m} \sum_{i=1}^n \ell(w; (x_i,y_i)) \]" src="form_255.png"/>
</p>
<p>where <img class="formulaInl" alt="$ x_i $" src="form_102.png"/> are data vectors in <img class="formulaInl" alt="$ \mathbb{R}^d $" src="form_156.png"/>, <img class="formulaInl" alt="$ y_i \in \{-1,1\} $" src="form_256.png"/> are binary labels, <img class="formulaInl" alt="$ \lambda > 0 $" src="form_257.png"/> is the regularization parameter, and</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \ell(w;(x_i,y_i)) = \max\{0, 1 - y_i \langle w,x_i\rangle\}. \]" src="form_258.png"/>
</p>
<p>is the <em>hinge loss</em>. The result of the optimization is a model <img class="formulaInl" alt="$ w \in \mathbb{R}^d $" src="form_259.png"/> that yields the decision function</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ F(x) = \operatorname{sign} \langle w, x\rangle. \]" src="form_260.png"/>
</p>
<p>It is well known that the hinge loss is a convex upper bound of the i01-loss of the decision function:</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \ell(w;(x,y)) \geq \frac{1}{2}(1 - y F(x)). \]" src="form_261.png"/>
</p>
<p>PEGASOS is accessed by calling <a class="el" href="pegasos_8h.html#a13544d1f72e8f428e9dbf0d20241b693">vl_pegasos_train_binary_svm_d</a> or <a class="el" href="pegasos_8h.html#a1c3c702bb19206c992fc166d82709c6b">vl_pegasos_train_binary_svm_f</a>, operating respectively on <code>double</code> or <code>float</code> data.</p>
<h3><a class="anchor" id="pegasos-algorithm"></a>
Algorithm</h3>
<p>PEGASOS <a class="el" href="citelist.html#CITEREF_shalev-shwartz07pegasos">[9]</a> is a stochastic subgradient optimizer. At the <em>t</em>-th iteration the algorithm:</p>
<ul>
<li>Samples uniformly at random as subset <img class="formulaInl" alt="$ A_t$" src="form_262.png"/> of <em>k</em> of training pairs <img class="formulaInl" alt="$(x,y)$" src="form_263.png"/> from the <em>m</em> pairs provided for training (this subset is called mini batch).</li>
<li>Computes a subgradient <img class="formulaInl" alt="$ \nabla_t $" src="form_264.png"/> of the function <img class="formulaInl" alt="$ E_t(w) = \frac{1}{2}\|w\|^2 + \frac{1}{k} \sum_{(x,y) \in A_t} \ell(w;(x,y)) $" src="form_265.png"/> (this is the SVM objective function restricted to the minibatch).</li>
<li>Compute an intermediate weight vector <img class="formulaInl" alt="$ w_{t+1/2} $" src="form_266.png"/> by doing a step <img class="formulaInl" alt="$ w_{t+1/2} = w_t - \alpha_t \nalba_t $" src="form_267.png"/> with learning rate <img class="formulaInl" alt="$ \alpha_t = 1/(\eta t) $" src="form_268.png"/> along the subgradient. Note that the learning rate is inversely proportional to the iteration numeber.</li>
<li>Back projects the weight vector <img class="formulaInl" alt="$ w_{t+1/2} $" src="form_266.png"/> on the hypersphere of radius <img class="formulaInl" alt="$ \sqrt{\lambda} $" src="form_269.png"/> to obtain the next model estimate <img class="formulaInl" alt="$ w_{t+1} $" src="form_270.png"/>: <p class="formulaDsp">
<img class="formulaDsp" alt="\[ w_t = \min\{1, \sqrt{\lambda}/\|w\|\} w_{t+1/2}. \]" src="form_271.png"/>
</p>
 The hypersfere is guaranteed to contain the optimal weight vector <img class="formulaInl" alt="$ w^* $" src="form_272.png"/> <a class="el" href="citelist.html#CITEREF_shalev-shwartz07pegasos">[9]</a> .</li>
</ul>
<p>VLFeat implementation fixes to one the size of the mini batches <img class="formulaInl" alt="$ k $" src="form_159.png"/>.</p>
<h3><a class="anchor" id="pegasos-bias"></a>
Bias</h3>
<p>PEGASOS SVM formulation does not incorporate a bias. To learn an SVM with bias, the each data vector <img class="formulaInl" alt="$ x $" src="form_92.png"/> can be extended by a constant component <img class="formulaInl" alt="$ B $" src="form_273.png"/> (called <code>biasMultiplier</code> in the code). In this case, the model <img class="formulaInl" alt="$ w $" src="form_274.png"/> has dimension <img class="formulaInl" alt="$ D + 1 $" src="form_275.png"/> and the SVM discriminat function is given by <img class="formulaInl" alt="$ F(x) = \operatorname{sign} (\langle w_{1:d}, x\rangle+ w_{d+1} B) $" src="form_276.png"/>. If the bias multiplier <em>B</em> is large enough, the weight <img class="formulaInl" alt="$ w_{d+1} $" src="form_277.png"/> remains small and it has small contribution in the SVM regularization term <img class="formulaInl" alt="$ \| w \|^2 $" src="form_278.png"/>, better approximating the case of an SVM with bias. Unfortunately, setting the bias multiplier <img class="formulaInl" alt="$ B $" src="form_273.png"/> to a large value makes the optimization harder.</p>
<h3><a class="anchor" id="pegasos-restarting"></a>
Restarting</h3>
<p>VLFeat PEGASOS implementation can be restatred after any given number of iterations. This is useful to compute intermediate statistics or to load new data from disk for large datasets. The state of the algorithm, which is required for restarting, is limited to the current estimate <img class="formulaInl" alt="$ w_t $" src="form_279.png"/> of the SVM weight vector and the iteration number <img class="formulaInl" alt="$ t $" src="form_280.png"/>.</p>
<h3><a class="anchor" id="pegasos-permutation"></a>
Permutation</h3>
<p>VLFeat PEGASOS can use a user-defined permutation to decide the order in which data points are visited (instead of using random sampling). By specifying a permutation the algorithm is guaranteed to visit each data point exactly once in each loop. The permutation needs not to be bijective. This can be used to visit certain data samples more or less often than others, implicitly reweighting their relative importance in the SVM objective function. This can be used to blanace the data.</p>
<h3><a class="anchor" id="pegasos-kernels"></a>
Non-linear kernels</h3>
<p>PEGASOS can be extended to non-linear kernels, but the algorithm is not particularly efficient in this setting [1]. When possible, it may be preferable to work with explicit feature maps.</p>
<p>Let <img class="formulaInl" alt="$ k(x,y) $" src="form_75.png"/> be a positive definite kernel. A <em>feature map</em> is a function <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> such that <img class="formulaInl" alt="$ k(x,y) = \langle \Psi(x), \Psi(y) \rangle $" src="form_281.png"/>. Using this representation the non-linear SVM learning objective function writes:</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \min_{w} \frac{\lambda}{2} \|w\|^2 + \frac{1}{m} \sum_{i=1}^n \ell(w; (\Psi(x)_i,y_i)). \]" src="form_282.png"/>
</p>
<p>Thus the only difference with the linear case is that the feature <img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> is used in place of the data <img class="formulaInl" alt="$ x $" src="form_92.png"/>.</p>
<p><img class="formulaInl" alt="$ \Psi(x) $" src="form_91.png"/> can be learned off-line, for instance by using the incomplete Cholesky decomposition <img class="formulaInl" alt="$ V^\top V $" src="form_283.png"/> of the Gram matrix <img class="formulaInl" alt="$ K = [k(x_i,x_j)] $" src="form_284.png"/> (in this case <img class="formulaInl" alt="$ \Psi(x_i) $" src="form_285.png"/> is the <em>i</em>-th columns of <em>V</em>). Alternatively, for additive kernels (e.g. intersection, Chi2) the explicit feature map computed by <a class="el" href="homkermap_8h.html">homkermap.h</a> can be used. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
